package com.fr.lintcode;

import org.junit.Test;

public class Q552iv {

	/**
	 * @param nums1: an integer array of length m with digits 0-9
	 * @param nums2: an integer array of length n with digits 0-9
	 * @param k:     an integer and k <= m + n
	 * @return: an integer array
	 */
	/**
	 * pick i from nums1(k - length2 < 0 ? 0 : k - length2 < i < k < length1 ? k :
	 * length1) pick k-i from nums2
	 * 
	 * merge pick a & b
	 */
	public int[] maxNumber(int[] nums1, int[] nums2, int k) {
		// write your code here
		if (k == 0) {
			return new int[0];
		}
		int length1 = nums1.length;
		int length2 = nums2.length;
		int[] rs = null;
		int left = k - length2;
		left = left < 0 ? 0 : left;
		int right = k > length1 ? length1 : k;
		for (int i = left; i <= right; i++) {
			int[] n1 = pick(nums1, i);
			int[] n2 = pick(nums2, k - i);
			int[] tmp = merge(n1, n2, k);
			rs = compare(rs, tmp);
		}
		return rs;
	}

	private int[] compare(int[] rs, int[] tmp) {
		if (rs == null) {
			return tmp;
		}
		for (int i = 0; i < rs.length; i++) {
			if (rs[i] > tmp[i]) {
				return rs;
			} else if (rs[i] < tmp[i]) {
				return tmp;
			}
		}
		return rs;
	}

	private int[] pick(int[] nums, int i) {
		if (i == 0) {
			return null;
		}
		int[] rs = new int[i];
		int length = nums.length;
		int index = -1;
		for (int j = 0; j < i; j++) {
			index = findMax(nums, index + 1, length - i + j);
			rs[j] = nums[index];
		}
		return rs;
	}

	private int findMax(int[] nums, int from, int to) {
		int i = from;
		for (int j = from + 1; j <= to; j++) {
			if (nums[i] < nums[j]) {
				i = j;
			}
		}
		return i;
	}

	private int[] merge(int[] nums1, int[] nums2, int k) {
		if (nums1 == null) {
			return nums2;
		}
		if (nums2 == null) {
			return nums1;
		}
		int rs[] = new int[k];
		int index = 0;
		int index1 = 0;
		int index2 = 0;
		while (index1 < nums1.length && index2 < nums2.length) {
			if (nums1[index1] > nums2[index2]) {
				rs[index++] = nums1[index1++];
			} else if (nums1[index1] < nums2[index2]) {
				rs[index++] = nums2[index2++];
			} else {
				// how to choose the right one?
				if (chooseA(nums1, nums2, index1, index2)) {
					rs[index++] = nums1[index1++];
				} else {
					rs[index++] = nums2[index2++];
				}

			}
		}
		while (index1 < nums1.length) {
			rs[index++] = nums1[index1++];
		}
		while (index2 < nums2.length) {
			rs[index++] = nums2[index2++];
		}
		return rs;
	}

	// TODO unknown bug to fix
	private boolean chooseA(int[] nums1, int[] nums2, int index1, int index2) {
		int l1 = index1;
		int l2 = index2;
		while (l1 < nums1.length && l2 < nums2.length && nums1[l1] == nums2[l2]) {
			l1++;
			l2++;
		}
//        if (l1 == nums1.length) {
//            if (l2 == nums2.length) {
//                return true;
//            } else {
//                return nums1[index1] >= nums2[l2];
//            }
//        } else {
//            if (l2 == nums2.length) {
//                return nums1[index1] <= nums1[l1];
//            } else {
//                return nums1[l1] >= nums2[l2];
//            }
//        }
		if (l2 == nums2.length) {
			return true;
		}
		if (l1 < nums1.length && nums1[l1] > nums2[l2]) {
			return true;
		}
		return false;
	}

	@Test
	public void TestA() {
//         [5,0,2,1,0,1,0,3,9,1,2,8,0,9,8,1,4,7,3], [7,6,7,1,0,1,0,5,6,0,5,0], 31
//         int[] a = { 5, 0, 2, 1, 0, 1, 0, 3, 9, 1, 2, 8, 0, 9, 8, 1, 4, 7, 3 };
//         int[] b = { 7, 6, 7, 1, 0, 1, 0, 5, 6, 0, 5, 0 };
//         int k = 31;
//		[3,4,6,5]
//				[9,1,2,5,8,3]
//				5
//        int[] a = {1};
//        int[] b = {};
//        int k = 1;
//         [2,0,2,1,2,2,2,2,0,1,0,0,2,0,2,0,2,1,0,1,1,0,1,0,1,2,1,1,1,0,1,2,2,1,0,0,1,2,1,2,2,1,1,0,1,2,0,2,0,1,2,0,2,1,1,1,2,0,0,1,0,2,1,2,0,1,0,0,0,1,2,1,0,1,1,2,0,2,2,0,0,1,1,2,2,1,1,2,2,1,0,1,2,0,1,2,2,0,0,0,2,0,2,0,2,2,0,1,1,1,1,2,2,2,2,0,0,2,2,2,2,0,2,0,1,0,0,2,1,0,0,2,0,2,1,1,1,1,0,1,2,0,2,1,0,1,1,1,0,0,2,2,2,0,2,1,1,1,2,2,0,0,2,2,2,2,2,0,2,0,2,0,2,0,0,1,0,1,1,0,0,2,1,1,2,2,2,1,2,2,0,0,2,1,0,2,1,2,1,1,1,0,2,0,1,1,2,1,1,0,0,1,0,1,2,2,2,0,2,2,1,0,1,2,1,2,0,2,2,0,1,2,2,1,2,2,1,1,2,2,2,2,2,1,2,0,1,1,1,2,2,2,0,2,0,2,0,2,1,1,0,2,2,2,1,0,2,1,2,2,2,0,1,1,1,1,1,1,0,0,0,2,2,0,1,2,1,0,0,2,2,2,2,1,0,2,0,1,2,0]
//        		 [1,1,1,0,0,1,1,0,2,1,0,1,2,1,0,2,2,1,0,2,0,1,1,0,0,2,2,0,1,0,2,0,2,2,2,2,1,1,1,1,0,0,0,0,2,1,0,2,1,1,2,1,2,2,0,2,1,0,2,0,0,2,0,2,2,1,0,1,0,0,2,1,1,1,2,2,0,0,0,1,1,2,0,2,2,0,1,0,2,1,0,2,1,1,1,0,1,1,2,0,2,0,1,1,2,0,2,0,1,2,1,0,2,0,1,0,0,0,1,2,1,2,0,1,2,2,1,1,0,1,2,1,0,0,1,0,2,2,1,2,2,0,0,0,2,0,0,0,1,0,2,0,2,1,0,0,1,2,0,1,1,0,1,0,2,2,2,1,1,0,1,1,2,1,0,2,2,2,1,2,2,2,2,0,1,1,0,1,2,1,2,2,0,0,0,0,0,1,1,1,2,1,2,1,1,0,1,2,0,1,2,1,2,2,2,2,0,0,0,0,2,0,1,2,0,1,1,1,1,0,1,2,2,1,0,1,2,2,1,2,2,2,0,2,0,1,1,2,0,0,2,2,0,1,0,2,1,0,0,1,1,1,1,0,0,2,2,2,2,0,0,1,2,1,1,2,0,1,2,1,0,2,0,0,2,1,1,0,2,1,1,2,2,0,1,0,2,0,1,0]
//        		 600
		int[] a = { 2, 0, 2, 1, 2, 2, 2, 2, 0, 1, 0, 0, 2, 0, 2, 0, 2, 1, 0, 1, 1, 0, 1, 0, 1, 2, 1, 1, 1, 0, 1, 2, 2,
				1, 0, 0, 1, 2, 1, 2, 2, 1, 1, 0, 1, 2, 0, 2, 0, 1, 2, 0, 2, 1, 1, 1, 2, 0, 0, 1, 0, 2, 1, 2, 0, 1, 0, 0,
				0, 1, 2, 1, 0, 1, 1, 2, 0, 2, 2, 0, 0, 1, 1, 2, 2, 1, 1, 2, 2, 1, 0, 1, 2, 0, 1, 2, 2, 0, 0, 0, 2, 0, 2,
				0, 2, 2, 0, 1, 1, 1, 1, 2, 2, 2, 2, 0, 0, 2, 2, 2, 2, 0, 2, 0, 1, 0, 0, 2, 1, 0, 0, 2, 0, 2, 1, 1, 1, 1,
				0, 1, 2, 0, 2, 1, 0, 1, 1, 1, 0, 0, 2, 2, 2, 0, 2, 1, 1, 1, 2, 2, 0, 0, 2, 2, 2, 2, 2, 0, 2, 0, 2, 0, 2,
				0, 0, 1, 0, 1, 1, 0, 0, 2, 1, 1, 2, 2, 2, 1, 2, 2, 0, 0, 2, 1, 0, 2, 1, 2, 1, 1, 1, 0, 2, 0, 1, 1, 2, 1,
				1, 0, 0, 1, 0, 1, 2, 2, 2, 0, 2, 2, 1, 0, 1, 2, 1, 2, 0, 2, 2, 0, 1, 2, 2, 1, 2, 2, 1, 1, 2, 2, 2, 2, 2,
				1, 2, 0, 1, 1, 1, 2, 2, 2, 0, 2, 0, 2, 0, 2, 1, 1, 0, 2, 2, 2, 1, 0, 2, 1, 2, 2, 2, 0, 1, 1, 1, 1, 1, 1,
				0, 0, 0, 2, 2, 0, 1, 2, 1, 0, 0, 2, 2, 2, 2, 1, 0, 2, 0, 1, 2, 0 };
		int[] b = { 1, 1, 1, 0, 0, 1, 1, 0, 2, 1, 0, 1, 2, 1, 0, 2, 2, 1, 0, 2, 0, 1, 1, 0, 0, 2, 2, 0, 1, 0, 2, 0, 2,
				2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 2, 1, 0, 2, 1, 1, 2, 1, 2, 2, 0, 2, 1, 0, 2, 0, 0, 2, 0, 2, 2, 1, 0, 1,
				0, 0, 2, 1, 1, 1, 2, 2, 0, 0, 0, 1, 1, 2, 0, 2, 2, 0, 1, 0, 2, 1, 0, 2, 1, 1, 1, 0, 1, 1, 2, 0, 2, 0, 1,
				1, 2, 0, 2, 0, 1, 2, 1, 0, 2, 0, 1, 0, 0, 0, 1, 2, 1, 2, 0, 1, 2, 2, 1, 1, 0, 1, 2, 1, 0, 0, 1, 0, 2, 2,
				1, 2, 2, 0, 0, 0, 2, 0, 0, 0, 1, 0, 2, 0, 2, 1, 0, 0, 1, 2, 0, 1, 1, 0, 1, 0, 2, 2, 2, 1, 1, 0, 1, 1, 2,
				1, 0, 2, 2, 2, 1, 2, 2, 2, 2, 0, 1, 1, 0, 1, 2, 1, 2, 2, 0, 0, 0, 0, 0, 1, 1, 1, 2, 1, 2, 1, 1, 0, 1, 2,
				0, 1, 2, 1, 2, 2, 2, 2, 0, 0, 0, 0, 2, 0, 1, 2, 0, 1, 1, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 2, 1, 2, 2, 2, 0,
				2, 0, 1, 1, 2, 0, 0, 2, 2, 0, 1, 0, 2, 1, 0, 0, 1, 1, 1, 1, 0, 0, 2, 2, 2, 2, 0, 0, 1, 2, 1, 1, 2, 0, 1,
				2, 1, 0, 2, 0, 0, 2, 1, 1, 0, 2, 1, 1, 2, 2, 0, 1, 0, 2, 0, 1, 0 };
		int k = 600;
		int[] rs = maxNumber(a, b, k);
		for (int s : rs) {
			System.out.print(s);
		}
	}
}
